//
//  main.cpp
//  hafuman
//
//  Created by 刘晨 on 2018/11/22.
//  Copyright © 2018 刘晨. All rights reserved.
//

#include <iostream>
using namespace std;
typedef struct node{
    int data;
    node * parent;
    node *lchild;
    node *rchild;
    node *next;
}node;

class Tree{
private:
    node* head;
    node *hufmTreeHead;
    int length;
#pragma 私有函数声明
    void inorderNode(node *p);
    void findMinNodeandDelete(node *&p);//找最小的结点并且删除掉
    void addNode(node *p1);//两个参数组成一个新的结点然后添加这个新的结点
public:
    Tree(){head = new node; head->lchild = head->rchild=head->parent=head->next =  NULL;hufmTreeHead = NULL; }
    void initTreeList();//创建一条链表
    void createHufmTree();
    void inorderTree();//中序遍历
    void printNode();//输出所有链表中的结点
};
#pragma 私有函数的实现开始
void Tree::inorderNode(node *p){
    if(p ==  NULL) return;
    else{
        inorderNode(p->lchild);
            cout<<"data: "<<p->data<<"\n";
        inorderNode(p->rchild);
    }
}
void Tree::findMinNodeandDelete(node *&p){
    cout<<"findMIn~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
    node *h1 = head;
    node *h = h1->next;
    int min = INT_MAX;
    while ( h != NULL) {
        if(h->data < min){
            min = h->data;
            p = h;
        }
        h = h->next;
    }
    h = h1->next;
    while (h != NULL) {
        if(h == p){
            h1->next = h->next;
            //并不能完全删除找到这个的结点，因为这个结点是要将来留在之后连接的；
            break;
        }
        h1 = h;
        h = h->next;
    }
    cout<<"min:"<<p->data<<"\n";
    length--;//删除一个结点length-1；
    printNode();
    cout<<"findMin________________________________________________\n";
}
void Tree::addNode(node *p){
    cout<<"add~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
    //头插法添加结点每次添加的都是在结点的头部
    p->next = head->next;
    head->next = p;
    length++;//添加一个新的结点length++;
    cout<<"添加的值:"<<p->data<<endl;
    printNode();
    cout<<"add___________________________________________\n";
    
}

#pragma 私有函数实现结束


#pragma 公有函数实现开始
void Tree::initTreeList(){
    cout<<"input data length:\n";
    
    int length;
    cin>>length;
    this->length = length;//数据长度
    
    cout<<"begin  input node data:\n";
    int data = 0;
    node *h = head;
    node* p;
    for (int i = 0; i<length; i++) {
        cout<<"input data: \t";
        cin>>data;
        p = new node;
        p->data= data;
        p->lchild = p->rchild=p->parent=p->next =  NULL;
        h->next = p;
        h = p;
        
    }
    
}
void Tree::createHufmTree(){
    node *p1,*p2;//找到的新结点
    while (length > 1) {
        findMinNodeandDelete(p1);
        findMinNodeandDelete(p2);
        cout<<p1->data<<p2->data;
        
        //        +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        node *n  = new node;//通过p1和p2组成一个新的结点;
        n->data = p1->data+p2->data;
        n->lchild = p1;
        n->rchild = p2;
        n->next = NULL;
        p1->parent = p2->parent = n;
        cout<<"createNode:"<<n->data<<endl;
        //        +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        addNode(n);
    }
    hufmTreeHead = head->next;
    cout<<"hufmanHead:"<<hufmTreeHead->data<<endl;
}

void Tree::inorderTree(){
    cout<<"inorderTree-------------------------------------------\n";
    node *p = hufmTreeHead;
    inorderNode(p);
    cout<<endl;
    cout<<"inorderTree___________________________________________\n";
}

void Tree::printNode(){
    cout<<endl;
    cout<<"printNode begin \n";
    node *h = head->next;
    cout<<"length"<<length<<";";
    while (h !=  NULL) {
        cout<<"h->data:"<<h->data<<endl;
        h = h->next;
    }
    cout<<"printNode finish\n";
}

#pragma 公有函数的实现的结束
int main(){
    Tree t;
    t.initTreeList();
    t.createHufmTree();
    t.inorderTree();
    return 1;
}
